//树与二叉树
#include <stdio.h>
#define maxSize 999
int main(int argc, char *argv[]) {
	/*树的基本概念*/
	/*
	树————许多结点的 集合————有唯一的根，和一些子树
			————结点为 0，则为空树
	
	结点————数据域， 指针域-指向子树及其分支
	结点的度————指向分支的指针 个数————即：指向的分支数
	树的度————各结点度 的最大值
	叶子结点//终端结点————度为 0 的结点
	分支结点//非终端结点————度不为 0 的结点
	孩子———— 指针域指向的 结点--可以有多个
	双亲———— 指向其的 结点--只可有一个
	兄弟———— 有同一个双亲的 结点
	祖先———— 从根 到 其自身，这一路上，所有的结点
	子孙———— 其自身 到 叶子结点，这一路上，所有的结点————子孙最多的一条路，子孙数 = 结点的高度
	层次/结点的深度———— 从根 到 其自身，一共经历的 结点个数————等于祖先的个数————
	树的高度/深度———— 树各结点的 最大层次
	堂兄弟———— 双亲在同一层的 结点
	森林———— 许多 互不相交的 树 的集合
	*/
	
	
	/*树的存储结构*/
	//1、顺序存储结构————双亲存储结构
	int tree[maxSize];//索引 表示 该结点的位置————数据 表示 双亲的位置
					  //只能存储结点的 位置信息————结点中的内容则 无法存储
	
	//2、链式存储结构————孩子存储结构、孩子兄弟存储结构————后面 详讲
	
	
	/***二叉树***/
	/*
	二叉树的定义：
	1、每个结点 最多两棵子树 ———— 结点的度 0 1 2
	2、子树 有 左右顺序之分
	
	满二叉树：
	分支结点的度————均为 2
	
	完全二叉树：
	对满二叉树各结点进行编号————完全二叉树在相同位置，结点编号与满二叉树 相同
	即：不考虑叶子结点————分支结点构成 满二叉树————即为 完全二叉树
	*/
	
	/*
	二叉树的主要性质：
	1、叶子结点数 == 双分支结点数+1
		拓展：
			度为1的结点数为n1--度为2的结点数为n2--度为3的结点数为n3----度为m的结点数为nm
			叶子结点数 = 1+ n2 + 2*n3 + …… + (m-1)*nm
	
	2、二叉树的i层上的 结点个数 <= 2^(i-1)
	
	3、树的高度为k的 满二叉树的结点个数 == 2^k-1
	
	4、完全二叉树 各结点从1开始编号
		编号为i的结点————双亲是i/2向下取整————左孩子2i————右孩子2i+1
	
	5、完全二叉树 有n个结点 高度为h：
			则  2^(h-1)-1 < n < 2^h-1
	*/
	
	/*二叉树的存储结构*/
	//1、顺序存储结构————适用于完全二叉树
	char binaryTree[maxSize];//用从1开始的 索引 表示 结点的位置； 用数组 存储 结点的数据
							//索引为i的结点————双亲是i/2向下取整————左孩子2i————右孩子2i+1	
}
	//2、链式存储结构
typedef struct binaryTreeNode
{
	char data;//存储结点数据
	
	struct binaryTreeNode *leftChild;//指向左孩子的 指针
	struct binaryTreeNode *rightChild;//指向右孩子 的指针
	
}binaryTreeNode;


/*二叉树的遍历*/
//1、先序遍历 ： 访问该结点 数据————访问左子树————访问右子树
void preOrderFind(binaryTreeNode *p)//p 指向要 访问的根结点
{
	if(p!=NULL)
	{
		printf("%c",p->data);//先 访问结点数据
		
		preOrderFind(p->leftChild);//再 先序访问 左子树
		preOrderFind(p->rightChild);//最后 先序访问 右子树
	}
}

//2、中序遍历 ： 访问左子树————访问该结点 数据————最后访问 右子树
void middleOrderFind(binaryTreeNode *p)
{
	if(p!=NULL)
	{
		middleOrderFind(p->leftChild);//先访问左子树
		
		printf("%c",p->data);//再 访问该结点 数据
		
		middleOrderFind(p->rightChild);//最后 访问 右子树
	}
}

//3、后序遍历 ： 访问左子树————再访问 右子树————最后访问该结点 数据
void lastOrderFind(binaryTreeNode *p)
{
	lastOrderFind(p->leftChild);
	lastOrderFind(p->rightChild);
	printf("%c",p->data);
}

//4、层次遍历————按层次，从左到右，自上而下，遍历
void levelFind(binaryTreeNode *p)//p指向 根结点
{
	//让各结点，自上而下，从左到右，逐一进队————先进先出
	
	//以下，创建一个空队列
	int front,rear;
	front = rear = 0;
	binaryTreeNode *queue[maxSize];//队列的成员为各结点————用指向他们的指针来 代指
	
	//先让 根结点 入队
	rear = (rear+1) % maxSize;
	queue[rear] = p;
	
	binaryTreeNode *q;//创造个辅助指针q，用来遍历各个结点
	
	while(rear != front)//队不为空时，进行出队操作
	{
		front = (front+1) % maxSize;
		q = queue[front];//重新 让q指针 定位到 下一个结点————进而让新结点的 孩子入队
		printf("%c",queue[front]->data);//结点出队，并读取 数据
		
		//让 左孩子入队
		if(q->leftChild != NULL)
		{
			rear = (rear+1) % maxSize;
			queue[rear] = q->leftChild;
		}
		
		//让 右孩子入队
		if(q->rightChild != NULL)
			{
				rear = (rear+1) % maxSize;
				queue[rear] = q->rightChild;
			}
	}
}


/**二叉树遍历算法的改进**/
/*1、二叉树深度优先遍历算法的非递归实现*/
//（1）先序遍历非递归算法 ： （ 结点入栈————其出栈————其右孩子、左孩子 分别入栈 ）循环执行
void preOrderNonrecursion(binaryTreeNode *p)//p指向根结点
{
	binaryTreeNode *stack[maxSize];
	int top = -1;//创造一个栈————存储结点（用指针代指）
	
	binaryTreeNode *q;//创造辅助指针，用来指向要输出的结点
	
	stack[++top] = p;//根结点入栈
	while(top!=-1)
	{
		q = stack[top--];//定位 将出栈的 结点
		printf("%c",q->data);//访问
		
		if(q->rightChild!=NULL)//入栈
			stack[++top] = q->rightChild;
		if(q->leftChild!=NULL)
			stack[++top] = q->leftChild;
	}
}

//（2）中序遍历非递归算法 ： （（结点入栈————左孩子入栈）循环————出栈————右孩子入栈）循环
void middleOrderNonrecursion(binaryTreeNode *p) //p指向根结点
{
	binaryTreeNode *stack[maxSize];
	int top = -1;//创造一个栈————存储结点（用指针代指）
	
	binaryTreeNode *q = p;//创造辅助指针，用来指向要输出的结点
	
	
	while(top!=-1||q!=NULL)
	{
		while(q!=NULL)//结点入栈————左孩子入栈）循环
		{
			stack[++top] = q;
			q = q->leftChild;
		}
		if(top!=-1)//出栈————右孩子入栈
		{
			q = stack[top--];
			printf("%c",q->data);//出栈，并访问
			q = q->rightChild;
		}
	}
}

//（3）后序遍历非递归算法 ：先序遍历 + 交换左右子树的遍历顺序 == 逆后序遍历 ———>利用栈输出，为后序遍历
void postOrderNonrecursion(binaryTreeNode *p) //p指向根结点
{
	binaryTreeNode *q = p;//创造辅助指针，用来指向要输出的结点
	
	binaryTreeNode *stack1[maxSize];
	int top1 = -1;//创造一个辅助栈————辅助（先序遍历 + 交换左右子树的遍历顺序）这个操作
	
	binaryTreeNode *stack2[maxSize];
	int top2 = -1;//创造一个栈————存储逆后序遍历时，依次 输出 的结点————逆向输出时，即为 后序遍历
	
	//以下，先序遍历 + 交换左右子树的遍历顺序————输出结点时，将该结点压入stack2
	stack1[++top1] = p;//根结点入栈
	while(top1!=-1)
		{
			q = stack1[top1--];//定位 将出栈的 结点
			stack2[++top2] = q;//访问
			
			//交换左右子树的遍历顺序
			if(q->leftChild!=NULL)
				stack1[++top1] = q->leftChild;
			if(q->rightChild!=NULL)//入栈
				stack1[++top1] = q->rightChild;
		}
	
	while(top2!=-1)//进行逆向输出
	{
		q = stack2[top2--];
		printf("%c",q->data);
	}
}


/*2、线索二叉树————把 二叉树 构造成 一个链表，从前到后输出即可*/
//（1）中序线索二叉树的构造
typedef struct clueBinaryTreeNode
{
	char data;
	struct clueBinaryTreeNode *leftChild;
	struct clueBinaryTreeNode *rightChild;//和普通二叉树一样
	
	int leftTag,rightTag;//作为线索标记
						 /*
							leftTag==0时，leftChild指向 左孩子 ； leftTag==1,leftChild指向 前驱
							rightTag==0时，rightChild指向 右孩子 ； rightTag==1,rightChild指向 后继
						*/
}clueBinaryTreeNode;

//通过中序遍历————对二叉树进行 线索化
void middleThread(clueBinaryTreeNode *p,clueBinaryTreeNode *pre)//p指向当前结点，pre指向 前驱结点
{
	if(p!=NULL)
	{
		middleThread(p->leftChild,pre);//递归————遍历左子树
		if(p->leftChild==NULL)//如果没有左孩子————则指向前驱
		{
			p->leftChild = pre;
			p->leftTag = 1;
		}
		if(pre!=NULL && pre->rightChild==NULL)//如果 前驱没有 右孩子————则指向后继
		{
			pre->rightChild = p;
			pre->rightTag = 1;
		}
		
		pre = p;
		middleThread(p->rightChild,pre);
	}
}
//有待完善……
//（2）遍历中序线索二叉树
//（3）前序线索二叉树
//（4）后序线索二叉树


/*** 树、森林和二叉树的互相转换 ***/
/* 
树转换为二叉树：
		1、将同一个结点的 孩子们 用虚线串起来
		2、从左往右，除第一个实线保留，其他实现均抹去
		3、将虚线 变成实线
*/
		
/*
二叉树转换为树：
		1、二叉树，自右上到左下，分为若干层
		2、每一层的结点，共同享有 一个双亲
		3、去除 兄弟结点之间的实线
*/

/*
森林转换为二叉树：
		1、将森林里的每棵树————>变成二叉树
		2、以第一课树的根结点 为二叉树的根结点————第一棵树根结点的右孩子，为第二棵树的根结点————第二棵树根结点的右孩子，为第三棵树的根结点————以此类推
*/
		
/*
二叉树转换成森林：
		1、断开根结点与右孩子的联系————产生新的根结点，再次断开与其右孩子的联系————直到有许多根结点没有右孩子的 二叉树
		2、利用二叉树转换为树的规则————>将二叉树全部变为树————>森林形成
*/

/*
树的遍历：
	（1）先序遍历：
			1、访问根结点
			2、访问与根结点相连的 子树
			3、访问子树时，重复上述操作
	（2）后序遍历：
			1、先依次访问根结点的每棵子树
			2、在访问根结点
			3、访问子树时，也依照上述顺序
*/

/*
森林的遍历：
	（1）先序遍历：
			1、先序遍历第一棵树
			2、先序遍历第二棵树
			3、以此类推
	（2）后序遍历/中序遍历
			1、后序遍历第一棵树
			2、后序遍历第二棵树
			3、以此类推
*/
			

/*** 树与二叉树的运用 ***/
//二叉排序树与平衡二叉树————放在 查找 一章讲

/*
赫夫曼树和赫夫曼编码：
	赫夫曼树————又称“最优二叉树”————带权路径最短
		1、路径：从一个结点 到另一个结点 所形成的线
		2、路径长度：在一个路径上，经过了多少结点
		3、树的路径长度：从根到每个结点的 路径长度之和
		4、带权路径长度：一个结点到根结点的路径长度 * 该结点的权值
		5、树的带权路径长度（WPL）：所有叶子结点的 带权路径长度之和
		
	赫夫曼树构造方法：
		给定n个权值————>构造赫夫曼树————可能不唯一
		1、将这n个权值，看作只有根结点的 一个个二叉树 ——> 形成集合F
		2、从F中，选出两个权值最小的树a、b————作为左右子树————构造全新二叉树c，新生的根结点权值为0
		3、从F中删除a、b， 将c加入F
		4、重复上述操作，直到 F中只有一个树————即为 赫夫曼树，WPL最小
	
	赫夫曼树的特点：
		1、权值越大的结点，离根结点越近
		2、没有度为1的结点————正则（严格）二叉树
	
	赫夫曼编码：
		1、以字符为根结点，以出现的次数为权值————>构造赫夫曼树
		2、让左子树为0，右子树为1————>根结点 到 各个字符结点 路径上的数字 按顺序排在一起————即为 该字符的 赫夫曼编码
		3、作用：使字符串 编码长度 变短
	
	赫夫曼n叉树：
		1、类推 赫夫曼二叉树的构造
		2、当结点不够时， 添加权值为0的结点 来凑数
*/